package tree.ordertraversal;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Classname : BinaryTreePostorderTraversal
 * @Description :
 * <a href="https://leetcode.cn/problems/binary-tree-postorder-traversal/">145. 二叉树的后序遍历</a>
 * @Author : chentianyu
 * @Date 2023/1/23 16:24
 */


public class BinaryTreePostorderTraversal {

    /**
     * 栈循环实现后序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> postorder = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.left == null && cur.right == null) postorder.add(cur.val);
            else {
                stack.push(new TreeNode(cur.val));
                if (cur.right != null) stack.push(cur.right);
                if (cur.left != null) stack.push(cur.left);
            }
        }
        return postorder;
    }


    /**
     * 递归实现后序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> postorder = new ArrayList<>();
        postorderTraversalHelper(postorder, root);
        return postorder;
    }

    private void postorderTraversalHelper(List<Integer> postorder, TreeNode root) {
        if (root == null) return ;

        postorderTraversalHelper(postorder, root.left);
        postorderTraversalHelper(postorder, root.right);
        postorder.add(root.val);
    }
}
